/*
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#pragma once

#include "NTree.h"

class NTreeHelpers
{
public:
	template<class VecType, class DataType>
	static int
	countSubNodes(const typename NTree<VecType, DataType>::Node& node)
	{
		int iSum=0;
		switch(node.getType())
		{
		case Solid:
		case Nil:
			return iSum;
		default:
			for (unsigned int i = 0; i < VecType::childCount; i++)
				iSum+=countSubNodes<VecType, DataType>(node.constGetSubNode(i));
			break;
		}
		return 1 + iSum;
	}


	template<class VecType, class DataType>
	static int
	countNodes(const NTree<VecType, DataType>& tree)
	{
		int iSum=0;
		for (unsigned int i = 0; i < VecType::childCount; i++)
			iSum+=countSubNodes<VecType, DataType>(tree.constGetRoot(i));
		return iSum;
	}

	template<class VecType, class DataType>
	static int
	countSubVoxels(const typename NTree<VecType, DataType>::Node& node,
			const Area<VecType>& area, double afCenterAccum[VecType::dimension])
	{
		int iSum=0;
		VecType center;
		switch(node.getType())
		{
		case Nil:
			return 0;
		case Solid:
			iSum = (int)powl(AuxMath::pow2(area.expo), VecType::dimension);

			center=area.toBox().center();
			for (unsigned int iDim = 0; iDim < VecType::dimension; iDim++)
				afCenterAccum[iDim]+=center[iDim]*iSum;
			break;
		default:
			Area<VecType> subAreas[VecType::childCount];
			area.subAreas(subAreas);
			for (unsigned int i = 0; i < VecType::childCount; i++)
			{
				int nSubVoxels=countSubVoxels<VecType, DataType>(node.constGetSubNode(i), subAreas[i], afCenterAccum);
				iSum+=nSubVoxels;
			}
			break;
		}
		return iSum;
	}


	template<class VecType, class DataType>
	static int
	countVoxels(const NTree<VecType, DataType>& tree, VecType& centerOfMass)
	{
		double afCenterAccum[VecType::dimension];
		memset(afCenterAccum, 0, sizeof(afCenterAccum));
		Area<VecType> subs[VecType::childCount];
		tree.subAreas(subs);
		int iSum=0;
		for (unsigned int i = 0; i < VecType::childCount; i++)
			iSum+=countSubVoxels<VecType, DataType>(tree.constGetRoot(i), subs[i], afCenterAccum);

		for (unsigned int iDim = 0; iDim < VecType::dimension; iDim++)
			centerOfMass[iDim]=(int)(afCenterAccum[iDim] * (1.0/iSum));
		return iSum;
	}

	template<class VecType, class DataType>
	static std::vector<std::pair<VecType, DataType>>
	getNodePoints(const typename NTree<VecType, DataType>::Node& node,
					const Area<VecType>& area)
	{
		//printf("Area %d %s\n{\n", area.expo, area.pos.toString().c_str());

		std::vector<std::pair<VecType, DataType>> result;
		bool bSolid=false;
		switch(node.getType())
		{
		case Nil:
			return result;
		case Solid:
			if(area.expo==0)
			{
				result.push_back(std::make_pair(area.pos, node.getData()));

				//printf("}\n");
				return result;
			}
			bSolid=true;
			//fall through
		default:
			Area<VecType> subAreas[VecType::childCount];
			area.subAreas(subAreas);
			if(bSolid)
			{
				for (unsigned int i = 0; i < VecType::childCount; i++)
				{
					auto points = getNodePoints<VecType, DataType>(node, subAreas[i]);
					result.insert(result.end(), points.begin(), points.end());
				}
			}
			else
			{
				for (unsigned int i = 0; i < VecType::childCount; i++)
				{
					auto points = getNodePoints<VecType, DataType>(node.constGetSubNode(i), subAreas[i]);
					result.insert(result.end(), points.begin(), points.end());
				}
			}
			break;
		}
		//printf("}\n");
		return result;
	}

	template<class VecType, class DataType>
	std::vector<std::pair<VecType, DataType>>
	static getPoints(const NTree<VecType, DataType>& tree)
	{
		Area<VecType> subs[VecType::childCount];
		tree.subAreas(subs);
		std::vector<std::pair<VecType, DataType>> resList;
		for (unsigned int i = 0; i < VecType::childCount; i++)
		{
			auto points = getNodePoints<VecType, DataType>(tree.constGetRoot(i), subs[i]);
			resList.insert(resList.end(), points.begin(), points.end());
		}
		return resList;
	}

	template <class VecType>
	static bool
	getBounds(Box<VecType>& res, std::vector<Box<VecType>>& vBoxes)
	{
		if(!vBoxes.size())
			return false;
		VecType	vMin=vBoxes[0].min,	vMax=vBoxes[0].max;
		for(unsigned int i=1; i<vBoxes.size(); i++)
			for(unsigned int iDim=0; iDim < VecType::dimension; iDim++)
			{
				if(vBoxes[i].min[iDim] < vMin[iDim])
					vMin[iDim]=vBoxes[i].min[iDim];
				if(vBoxes[i].max[iDim] > vMax[iDim])
					vMax[iDim]=vBoxes[i].max[iDim];
			}
		res.min=vMin;
		res.max=vMax;
		return true;
	}

	template<class VecType, class DataType>
	static bool
	getSubExtents(Box<VecType>& res, const typename NTree<VecType, DataType>::Node& node,
			const Area<VecType>& area)
	{
		Box<VecType> box;
		switch(node.getType())
		{
		case Nil:
			return false;
		case Solid:
			//printf("Area %d %s is solid.\n", area.expo, area.pos.toString().c_str());
			res=area.toBox();
			return true;
		default:
			Area<VecType> subAreas[VecType::childCount];
			area.subAreas(subAreas);
			std::vector<Box<VecType>> vBoxes;
			for (unsigned int i = 0; i < VecType::childCount; i++)
			{
				if(getSubExtents<VecType, DataType>(box, node.constGetSubNode(i), subAreas[i]))
					vBoxes.push_back(box);
			}
			return getBounds(res, vBoxes);
		}
	}

	//bool: has extents or is empty
	template<class VecType, class DataType>
	static bool
	getExtents(Box<VecType>& res, const NTree<VecType, DataType>& tree)
	{
		Area<VecType> subs[VecType::childCount];
		tree.subAreas(subs);
		std::vector<Box<VecType>> vBoxes;
		Box<VecType> box;
		for (unsigned int i = 0; i < VecType::childCount; i++)
		{
			if(getSubExtents<VecType, DataType>(box, tree.constGetRoot(i), subs[i]))
				vBoxes.push_back(box);
		}
		return getBounds(res, vBoxes);
	}


	template<class VecType, class DataType>
	static void
	createArrayRecursion(NTree<VecType, DataType>& res, VecType vOffset, VecType vShift, DataType t, int aiCount[VecType::dimension], unsigned int iDimension)
	{
		if(iDimension>=VecType::dimension)
		{
			res.insertVoxel(Area<VecType>(0, vOffset), t);
			return;
		}
		VecType vShiftDim=VecType(0);
		vShiftDim[iDimension]=vShift[iDimension];
		for (int i = 0; i < aiCount[iDimension]; i++)
			createArrayRecursion<VecType, DataType>(res, vOffset + vShiftDim * i, vShift, t, aiCount, iDimension+1);
	}
	
	template<class VecType, class DataType>
	static void
	createArray(NTree<VecType, DataType>& res, VecType vShift, DataType t, int aiCount[VecType::dimension])
	{
		//center array around (0,0,0)
		VecType vOffset(0);
		for (unsigned int iDim = 0; iDim < VecType::dimension; iDim++)
		{
			if(!aiCount[iDim])
				return;
			vOffset[iDim] = vShift[iDim] * (aiCount[iDim]-1);
		}
		vOffset = vOffset.half().reverse();

		res=NTree<VecType, DataType>(AuxMath::log2(vOffset.maxComponent())+1);
		createArrayRecursion<VecType, DataType>(res, vOffset, vShift, t, aiCount, 0);
	}

	template<class VecType, class DataType>
	static void
	invertSubVoxels(typename NTree<VecType, DataType>::Node& node,
			const Area<VecType>& area)
	{
		switch(node.getType())
		{
		case Nil:
			node=typename NTree<VecType, DataType>::Node(Solid);
			break;
		case Solid:
			node=typename NTree<VecType, DataType>::Node(Nil);
			break;
		default:
			Area<VecType> subAreas[VecType::childCount];
			area.subAreas(subAreas);
			for (unsigned int i = 0; i < VecType::childCount; i++)
				invertSubVoxels<VecType, DataType>
					(node.getSubNode(i), subAreas[i]);
			break;
		}
	}


	template<class VecType, class DataType>
	static void
	invertVoxels(NTree<VecType, DataType>& tree)
	{
		Area<VecType> subs[VecType::childCount];
		tree.subAreas(subs);
		for (unsigned int i = 0; i < VecType::childCount; i++)
			invertSubVoxels<VecType, DataType>(tree.getRoot(i), subs[i]);
	}

	template<class VecType, class DataType>
	static void
	checkNodes(const typename NTree<VecType, DataType>::Node& node,
			const Area<VecType>& area)
	{
		if(node.getType() == Both)
		{
			if(area.expo==0)
			{
				puts ("checkTree: Both node on level 0!");
				return;
			}
			Area<VecType> subAreas[VecType::childCount];
			area.subAreas(subAreas);
			unsigned int nSolid = 0, nNil = 0;

			for (unsigned int i = 0; i < VecType::childCount; i++)
			{
				checkNodes<VecType, DataType>(node.constGetSubNode(i), subAreas[i]);
				if(node.constGetSubNode(i).getType()==Nil)
					nNil++;
				else if(node.constGetSubNode(i).getType()==Solid)
					nSolid++;
			}
			if(nNil == 8)
				printf("non-simplified Nils found (level %d)\n", area.expo);
			if(nSolid == 8)
				printf("non-simplified Solids found (level %d)\n", area.expo);
		}
	}

	template<class VecType, class DataType>
	static void
	checkTree(const NTree<VecType, DataType>& tree)
	{
		Area<VecType> subs[VecType::childCount];
		tree.subAreas(subs);
		for (unsigned int i = 0; i < VecType::childCount; i++)
			checkNodes<VecType, DataType>(tree.constGetRoot(i), subs[i]);
		printf("check finished!\n");
	}

	template<class VecType, class DataType>
	static void
	trimNodes(typename NTree<VecType, DataType>::Node& node,
			const Area<VecType>& area,
			unsigned int uiMaxLevel, unsigned int uiTreeSize)
	{
		if(node.getType() == Both)
		{
			if(area.expo < (int)uiTreeSize - (int)uiMaxLevel)
			{
				node.destroySubNodes();
				node=typename NTree<VecType, DataType>::Node(Solid);
			}

			Area<VecType> subAreas[VecType::childCount];
			area.subAreas(subAreas);
			for(unsigned int i = 0; i < VecType::childCount; i++)
				trimNodes<VecType, DataType>
					(node.getSubNode(i), subAreas[i], uiMaxLevel, uiTreeSize);
		}
	}


	template<class VecType, class DataType>
	static void
	trimTree(NTree<VecType, DataType>& tree, unsigned int uiMaxLevel)
	{
		Area<VecType> subs[VecType::childCount];
		tree.subAreas(subs);
		for (unsigned int i = 0; i < VecType::childCount; i++)
			trimNodes<VecType, DataType>(tree.getRoot(i), subs[i], uiMaxLevel, tree.getSize());
	}
};
